package com.chaosj.algorithm

/**
 * @Description:
 * @author: caoyangjie
 * @date: 2019年11月2019/11/14日 17:10
 * @Copyright: © 赢时胜
 */
class AddTwoNumber {
    /**
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     *
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * 示例：
     *
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * @param args
     */
    static void main(String[] args){
        ListNode l1 = new ListNode(2)
        ListNode l2 = new ListNode(4)
        ListNode l3 = new ListNode(6)
        l2.next=l3
        l1.next=l2

        ListNode r1 = new ListNode(5)
        ListNode r2 = new ListNode(5)
        ListNode r3 = new ListNode(4)
        r2.next = r3
        r1.next = r2

        System.out.println(addTwoNumbers(l1,r1))
    }

    static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        System.out.println(solution1(l1,l2))
        solution2(l1,l2)
    }

    static ListNode solution1(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0)
        ListNode curr = result
        int carry = 0
        while (l1!=null || l2!=null){
            int x = l1!=null ? l1.val : 0
            int y = l2!=null ? l2.val : 0
            int sum = carry + x + y
            carry = sum / 10
            sum = sum % 10
            curr.next = new ListNode(sum)
            curr = curr.next
            if( l1!=null ){
                l1 = l1.next
            }
            if( l2!=null ){
                l2 = l2.next
            }
        }
        if( carry == 1 ){
            curr.next = new ListNode(carry)
        }
        result.next
    }

    static ListNode solution2(ListNode l1, ListNode l2) {
        return null
    }

    static class ListNode {
        int val
        ListNode next
        ListNode(int x) {
            val = x
        }


        @Override
        String toString() {
            return (next!=null?next.toString():"")+val
        }
    }
}
